package dijkstra;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

import arvore.ArvorePrim;

import graph.Graph;
import graph.Vertex;

public class Dijkstra {
	
	private Graph graph;
	
	private Vertex inicial;
	
	private ArrayList<ArvorePrim> fila = new ArrayList<>();
	
	private HashMap<Vertex,ArvorePrim> custoAntecessor = new HashMap<>();
	
	private HashSet<Vertex> calculados = new HashSet<>();
	
	public Dijkstra(Graph graph, Vertex inicial) {
		this.graph = graph;
		this.inicial = inicial;
		inicializa();
		dijkstra();
		imprimeArvore();
	}
	
	private void hashTOArray(){
		for (Entry<Vertex,ArvorePrim> entry:custoAntecessor.entrySet()){
			fila.add(new ArvorePrim(entry.getKey(), entry.getValue().getAntecessor(), entry.getValue().getValor()));
		}
	}
	
	private void imprimeArvore(){
		hashTOArray();
		Collections.sort(fila);
		for (ArvorePrim e:fila){
			String idv = e.getVertex().getId();
			String pi;
			if (e.getAntecessor() != null){
				pi = e.getAntecessor().getId();
			} else {
				pi = "-1";
			}
			double custo = e.getValor();
			graph.getSolucao().add(pi+" "+idv);
			//System.out.println(pi+ " "+ idv + " "+ custo);
		}
	}
	
	private void inicializa(){
		for (Entry<String, Vertex> u: graph.getGraphVertex().entrySet()){
			ArvorePrim elemento = new ArvorePrim(null,Double.POSITIVE_INFINITY);
			custoAntecessor.put(u.getValue(),elemento);
			elemento.setVertex(u.getValue());
			fila.add(elemento);
		}
		custoAntecessor.get(inicial).setValor(0d);
		custoAntecessor.get(inicial).setAntecessor(null);
	}
	
	private void dijkstra(){
		while (!fila.isEmpty()){
			Collections.sort(fila);
			inicial = fila.get(0).getVertex();
			calculados.add(inicial);
			fila.remove(0);
			for (Vertex v : inicial.getAdjacentList()){
				relaxa(v);
			}
			
		}
	}
	
	private void relaxa(Vertex adj){
		double custoAresta = graph.adjacentAux(inicial, adj).getValor();
		if (custoAntecessor.get(adj).getValor() > custoAntecessor.get(inicial).getValor()+custoAresta){
			custoAntecessor.get(adj).setValor(custoAntecessor.get(inicial).getValor()+custoAresta);
			custoAntecessor.get(adj).setAntecessor(inicial);
		}
	}
	
}
